public class Solution712 {
    public int minimumDeleteSum(String s1, String s2) {
        int[][] f=new int[s1.length()+1][s2.length()+1];
        f[0][0]=0;
        for (int i=1;i<=s1.length();i++){
            f[i][0]=f[i-1][0]+s1.charAt(i-1);
        }
        for (int i=1;i<=s2.length();i++){
            f[0][i]=f[0][i-1]+s2.charAt(i-1);
        }
        for (int i=1;i<=s1.length();i++){
            for (int j=1;j<=s2.length();j++){
                f[i][j]=Math.min(f[i-1][j]+s1.charAt(i-1),f[i][j-1]+s2.charAt(j-1));
                f[i][j]=Math.min(f[i][j],f[i-1][j-1]+(s1.charAt(i-1)==s2.charAt(j-1)?0:s1.charAt(i-1)+s2.charAt(j-1)));
            }
        }
        return f[s1.length()][s2.length()];
    }

    public static void main(String[] args) {
        System.out.println(new Solution712().minimumDeleteSum("sea","eat"));
    }
}
